package com.lw.leetcode.dp.b;

/**678. 有效的括号字符串
 * @Author liw
 * @Date 2021/9/12 18:38
 * @Version 1.0
 */
public class CheckValidString {

    public static void main(String[] args) {
        CheckValidString test = new CheckValidString();

        // true
//        String str = "()";

        // true
//        String str = "(*)";

        // true
//        String str = "(*))";

        // true
//        String str = "((((()(()()()*()(((((*)()*(**(())))))(())()())(((())())())))))))(((((())*)))()))(()((*()*(*)))(*)()";

        // true
//        String str = "*)()";
        String str = "()(*";

        boolean b = test.checkValidString(str);
        System.out.println(b);
    }

    public boolean checkValidString(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '*') {
                dp[i][i] = true;
            }
        }
        for (int i = 1; i < n; i++) {
            char c1 = s.charAt(i - 1), c2 = s.charAt(i);
            dp[i - 1][i] = (c1 == '(' || c1 == '*') && (c2 == ')' || c2 == '*');
        }
        for (int i = n - 3; i >= 0; i--) {
            char c1 = s.charAt(i);
            for (int j = i + 2; j < n; j++) {
                char c2 = s.charAt(j);
                if ((c1 == '(' || c1 == '*') && (c2 == ')' || c2 == '*')) {
                    dp[i][j] = dp[i + 1][j - 1];
                }
                for (int k = i; k < j && !dp[i][j]; k++) {
                    dp[i][j] = dp[i][k] && dp[k + 1][j];
                }
            }
        }
        return dp[0][n - 1];
    }

}
